/*#
 #*/
package cn.itaha.algorithm.leetcode.dynamicprogramming;

/**
 * <p>标题：计算各个位数不同的数字个数</p>
 * <p>功能：</p>
 * <pre>
 * 其他说明：
 * 地址链接：https://leetcode-cn.com/problems/count-numbers-with-unique-digits/
 * </pre>
 * <p>创建日期：2019年12月3日下午5:46:49</p>
 * <p>类全名：cn.itaha.algorithm.leetcode.dynamicprogramming.Code357CountNumbersWithUniqueDigits</p>
 * 查看帮助：<a href="" target="_blank"></a> 
 *
 * 作者：yinjun
 * 初审：
 * 复审：
 * @version 1.0
 */
public class Code357CountNumbersWithUniqueDigits
{
	public static void main(String[] args)
	{
		/**
		 * 给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。

		示例:

		输入: 2
		输出: 91 
		解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。
		 */
		int countNumbersWithUniqueDigits = countNumbersWithUniqueDigits(3);
		System.out.println(countNumbersWithUniqueDigits);
	}

	/**
	 * 本题采用动态规划思路(借鉴参考题解里他人解答的思路):
	 * 		高位数值总可以看成由低位数值后加n位数字组成,如：
	 * 			高位数：998		低位数：99*10+8
	 * 			因此问99组成高位数值有几种可能：
	 * 				99n=990 991 992 993 994 995 996 997 998 999 即 10种可能
	 *		结合本题来看：
	 *			我们将n位数看成高位数值，将n-1,n-2等等看成低位数值
	 *			例如：现在求n=2的本题解
	 *			则：
	 *				n=0时的数字有：{0}
	 *				n=1时的数字有：{0,1,2,3,4,5,6,7,8,9}
	 *			因此，n=2的数字可看成是n=1时的数字+除去9之后的数字到100-重复数字位的数字
	 *			而除去9之后的数字到100,可看成：
	 *				n=1时的数字后面再加一位，由于是多位数字，因此排除0，即得：
	 *				{1*10+(0到9),2*10+(0到9),3*10+(0到9),4*10+(0到9),5*10+(0到9),6*10+(0到9),7*10+(0到9),8*10+(0到9),9*10+(0到9)}
	 *			由于要去除重复数字，此时低位数值是1位,则意味着不要和这1位的数字重复就行了
	 *			则记dp[i]表示i位数字时，各位非重复的数字个数：
	 *			初始化dp[0]=1,dp[1]=10
	 *			则:
	 *				dp[i]=dp[i-1]+(dp[i-1]-dp[i-2])*(10-(i-1))
	 *				dp[i-1]-dp[i-2]：
	 *					由之前的分析可知，i位的数字是由i-1的数字*10+0到9组成，这个i-1的数字又需要剔除i-2位的数字，比如：
	 *						求i=3
	 *						则i=2的数字是0到100之间各位不重复数字的数字
	 *						则100到1000之间的不重复数字可看成是i=2时，10-100之间不重复的数字*10+其他数字组成
	 *						因此这里是dp[i-1]-dp[i-2],相当于是只取10-100之间的，排除0-10的数字一个道理
	 *				10-(i-1):
	 *					表示可搭配的数字个数，比如一般来说，可搭配的数字是0到9，但是这里是去掉重复数字的可能组合
	 *					并且我们是求数字的个数，并不求数字的具体值，因此我们可以不用管0到9中哪些数字和前面i-1位组成的数字是重复的，
	 *					只需要知道前面是多少位数字，那么0到9中就有多少个数字可能会组成重复的，比如：
	 *						i=3   前i-1位，举例个数字：98   则0到9中组成重复的数字有9和8两种情况，即有i-1位数字时，0到9中就有i-1个数字有组成重复的情况
	 *						而一共有10个数字，因此是10-(i-1)
	 *				而前面i-1位数字需要组合的个数是dp[i-1]-dp[i-2]
	 *				因此i位数字的不重复组合个数是dp[i-1]-dp[i-2]*(10-(i-1))
	 *				再加上i-1位数字的个数，即
	 *					dp[i]=dp[i-1]+(dp[i-1]-dp[i-2])*(10-(i-1))
	 *				
	 * 时间复杂度：O(n)
	 * 空间复杂度：O(n)
	 *				
	 * @param n
	 * @return
	 */
	public static int countNumbersWithUniqueDigits(int n)
	{
		if (n == 0)
		{
			return 1;
		}
		if (n == 1)
		{
			return 10;
		}
		int[] dp = new int[n + 1];
		dp[0] = 1;
		dp[1] = 10;
		for (int i = 2; i < dp.length; i++)
		{
			//3 预期：739
			dp[i] = dp[i - 1] + (dp[i - 1] - dp[i - 2]) * (10 - (i - 1));
		}
		for (int i = 0; i < dp.length; i++)
		{
			System.out.print(dp[i] + "\t");
		}
		System.out.println();
		return dp[n];
	}
}
